package sort;

import java.util.Arrays;

/**
 * 快速排序
 */
public class FastSort {

    public static void main(String[] args) {
        int[] arr = {2,54,1,33,23,23,23,23,23,23,4};
        fastSort(arr,0,arr.length-1);
    }
    public static void fastSort(int[] arr,int L,int R){
        if (L < R){
            // 交换最后一个值和数组中的一个随机值，与随机值作比较
            swap(arr,R,L+(int)(Math.random()*(R-L+1)));
            // 找到数组对应区段的 ==num的右边界，和==num的左边界，返回
            // 中间的就是=num的，不需要再排序了
            int[] p = partition(arr,L,R);
            // 排<num区的
            fastSort(arr,L,p[0]-1);
            // 排>num区的
            fastSort(arr,p[1]+1,R);
        }
    }
    public static int[] partition(int[] arr,int L,int R){
        int num = arr[R];
        int left = L;
        int right = R;
        int i = L;
        while (i <= right){
            if (arr[i] < num){
                swap(arr,i++,left++);
            }else if (arr[i] > num){
                swap(arr,i,right--);
            }else{
                i++;
            }
        }
        int[] p = {left,right};
        return p;
    }
    public static void swap(int[] arr,int i,int j){
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}
